UVa/321 - The New Villa/321.2.cpp

   1 /*
   2   Accepted, slower.
   3  */
   4 #include <iostream>
   5 #include <cassert>
   6 #include <queue>
   7 #include <vector>
   8 #include <algorithm>
   9 #include <iterator>
  10
  11 using namespace std;
  12
  13 struct state{
  14   int i, lights, w;
  15   vector<string> path;
  16   state() {}
  17   state(int I, int L, int W) : i(I), lights(L), w(W) {}
  18 };
  19
  20 const int MAXR = 10;
  21
  22 int toggleBit(int x, int b){
  23   if (x & (1 << b))
  24     return x & ~(1 << b);
  25   else
  26     return x | (1 << b);
  27 }
  28
  29 int differentBit(int x, int y){
  30   return __builtin_ctz(x ^ y);
  31 }
  32
  33 int main(){
  34   int r, d, s, C = 1;
  35   while (scanf("%d%d%d", &r, &d, &s) == 3 && (r+d+s)){
  36     vector<int> doors[r], switches[r];
  37     printf("Villa #%d\n", C++);
  38
  39     for (int i=0; i<d; ++i){
  40       int u, v;
  41       scanf("%d%d", &u, &v);
  42       --u, --v;
  43       doors[u].push_back(v);
  44       doors[v].push_back(u);
  45     }
  46
  47     for (int i=0; i<s; ++i){
  48       int u, v;
  49       scanf("%d%d", &u, &v);
  50       --u, --v;
  51       switches[u].push_back(v);
  52     }
  53
  54     bool visited[(1<<MAXR)+1][MAXR] = {false};
  55
  56     queue<state> q;
  57     q.push(state(0, 1<<0, 0));
  58     bool solved = false;
  59     while (q.size()){
  60       state u = q.front();
  61       //printf("popped state: i = %d, lights = %X, w = %d\n", u.i, u.lights, u.w);
  62       q.pop();
  63       if (u.i == r - 1 && u.lights == (1 << (r-1))){
  64         //Solution found
  65         solved = true;
  66         //printf("u.path.size() = %d, u.w = %d\n", u.path.size(), u.w);
  67         assert(u.path.size() == u.w);
  68         //printf("Solution found. i = %d, lights = %X, w = %d\n", u.i, u.lights, u.w);
  69         printf("The problem can be solved in %d steps:\n", u.w);
  70         copy(u.path.begin(), u.path.end(), ostream_iterator<string>(cout, ""));
  71         break;
  72       }
  73
  74       if (visited[u.lights][u.i]) continue;
  75       visited[u.lights][u.i] = true;
  76
  77       vector<int> &s = switches[u.i];
  78       for (int j=0; j<s.size(); ++j){
  79         int nlights = toggleBit(u.lights, s[j]);
  80         if (!visited[nlights][u.i] && (nlights & (1 << u.i))){
  81           q.push(state(u.i, nlights, u.w + 1));
  82           char buf[256];
  83           sprintf(buf, "- Switch %s light in room %d.\n", (nlights > u.lights ? "on" : "off"), differentBit(u.lights, nlights) + 1);
  84           q.back().path = u.path;
  85           q.back().path.push_back(string(buf));
  86           //printf("  pushed state: i = %d, lights = %X, w = %d\n", u.i, nlights, u.w + 1);
  87         }
  88       }
  89
  90       vector<int> &d = doors[u.i];
  91       for (int j=0; j<d.size(); ++j){ //Moverme sin apagar luces
  92         if (!visited[u.lights][d[j]] && (u.lights & (1 << d[j]))){
  93           q.push(state(d[j], u.lights, u.w + 1));
  94           char buf[256];
  95           sprintf(buf, "- Move to room %d.\n", d[j] + 1);
  96           //printf("  pushed state: i = %d, lights = %X, w = %d\n", d[j], u.lights, u.w + 1);
  97           q.back().path = u.path;
  98           q.back().path.push_back(string(buf));
  99         }
 100       }
 101     }
 102
 103     if (!solved) printf("The problem cannot be solved.\n");
 104     printf("\n");
 105   }
 106   return 0;
 107 }